五色定理是圖論中的一個結論:將一個平面分成若干區域,給這些區域染色,且保證任意相鄰區域沒有相同顏色,那麼所需顏色不超過五種。五色定理比四色定理弱,也比四色定理更容易證明。1879年,阿爾弗雷德·布雷·肯普給出了四色定理的一個證明,當時為人所接受,但11年後,珀西·約翰·希伍德卻發現了肯普的證明中存在錯誤,他把肯普的證明加以修改,得到了五色定理。
以下是對五色定理的證明[1]。
給定
階平面圖
,我們對
的階數進行歸納證明。
當
時,正確性顯然。
假設
且對於任意的
階平面圖該結論成立。因為
是平面圖,那麼存在點
,滿足
(通過歐拉公式可知對任意平面圖
,
)。
考慮圖
。因為
,由歸納假設知
能進行5-着色。假設
使用
五種顏色着色。考慮
的相鄰點,如果在
中它們用了不到五種顏色着色,那麼我們從剩下的顏色中選一個為
着色,就得到了
的一個5-着色方式。如果在
中它們用上了所有五種顏色,這就意味着
有且僅有5個相鄰點(
),從順時針方向我們依次稱它們為
,不失一般性,假設
的顏色為
。
我們希望通過調整
的着色方式,使得
有色可染。考慮
中所有顏色為
或
的點。
- 如果
中不存在這樣一條連接
與
的路徑,路徑上所有點的顏色均為
或
。定義
是滿足以下條件的所有路徑的併集:以
為起點且路徑上所有點的顏色均為
或
。注意到
。此時我們可以將
中所有點的顏色互換:把
換成
,把
換成
。交換之後也是
的一個5-着色方式。此時
的顏色變成了
,我們將
染為
。因此,
能進行5-着色。
- 如果
中存在這樣一條連接
與
的路徑,路徑上所有點的顏色均為
或
,我們稱之為
。注意到
與
共同形成了一個環,這個環要麼把
要麼把
圈在裏面。此時我們發現,不存在這樣一條連接
與
的路徑,路徑上所有點的顏色均為
或
。我們只需按照情況1中的方式調整顏色即可。因此,
能進行5-着色。
綜上所述,
能進行5-着色。
參考資料[編輯]
- Heawood, P. J., Map-Colour Theorems, Quarterly Journal of Mathematics, Oxford 24, 1890, 24: 332–338
- ^ Harris, John; Hirst, Jeffry L.; Mossinghoff, Michael, Combinatorics and Graph Theory, Undergraduate Texts in Mathematics, Springer-Verlag New York: 98–99, 2008, ISBN 978-0-387-79711-3, doi:10.1007/978-0-387-79711-3